﻿//#define TRACE_1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions.Problems
{
    /*
     * 

Given the positive integers, x, y, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x2 − y2 − z2 = n, has exactly two solutions is n = 27:

342 − 272 − 202 = 122 − 92 − 62 = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?

     * */
    class Problem135 : IProblem //isti kao problem 136, drugi brojevi ...
    {
        public string Calculate()
        {
            int limit = 50000000;
            int[] solutions = new int[limit];

            long d = 0;
            while (true)
            {
                d++;

                if (d == 501)
                {

                }

                long a = -1;
                long b = 2 * d;
                long c = 3 * d * d;

                bool hadOne = false;

                long x = (long)((-b - Math.Sqrt(b * b - 4 * a * c)) / (2.0 * a));
                while (true)
                {
                    x--;

                    if (x <= 0)
                        break;

                    long n = 2 * x * d + 3 * d * d - x * x;
                    if (n >= limit)
                    {
                        x = (long)((-b + Math.Sqrt(b * b - 4 * a * (c - limit))) / (2.0 * a));
                        while (2 * x * d + 3 * d * d - x * x < limit)
                            x++;
                        continue;
                    }

                    //if (n <= 0)
                    //    break;

                    hadOne = true;


#if TRACE_1
                    if (d > 500)
                    {
                        Console.WriteLine("{0}^2 - {1}^2 - {2}^3 = {3}", x + 2 * d, x + d, x, n);
                        if(x<555)
                        Console.ReadKey();
                    }
#endif

                    solutions[n]++;
                }

                if (!hadOne)
                {
                    break;
                }
            }

            Console.WriteLine(solutions[1155]);

            return solutions.Where(y => y == 1).Count().ToString();
        }
    }
}
